package com.neverGiveUp.leetCode.arraySection;

public class algorithm {
    public static void main(String[] args) {
        // 	453. 最小移动次数使数组元素相等
        System.out.println(minMovesOptimal(new int[]{0, 0, 100}));


        // 665. 非递减数列 给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
        System.out.println(checkPossibility(new int[]{4, 5, 3}));

        // 283. 移动零 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。
        moveZeroes(new int[]{1, 0, 2, 0, 2, 0});


    }

    /**
     * 给定一个数组，每次只能减一个值，将数组的每个值都减到最小值 一共需要多少次
     *
     * @param nums
     * @return
     */
    public static int minMovesOptimal(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int resNum = 0;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            if (min > num) min = num;
        }
        for (int i : nums) {
            resNum += i - min;
        }
        return resNum;
    }

    public static boolean checkPossibility(int[] nums) {
        if (nums.length < 3) {
            return true;
        }
        int count = 0;
        for (int i = 0; i < nums.length - 1; i++) {

            if (nums[i] > nums[i + 1]) {
                count++;
                if (count > 1) {
                    break;
                }
                if (i > 0 && nums[i - 1] > nums[i + 1]) {
                    nums[i + 1] = nums[i];
                } else {
                    nums[i] = nums[i + 1];
                }
            }
        }
        return count <= 1;
    }


    public static boolean checkPossibility2(int[] nums) {
        int n = nums.length;
        if (n <= 1) return true;
        int down = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] < nums[i - 1]) {
                down++;
                if (down > 1) {
                    return false;
                }
                if (i > 1 && i < n - 1 && nums[i - 1] > nums[i + 1] && nums[i - 2] > nums[i]) {
                    return false;
                }
            }
        }
        return true;
    }


    /**
     * 笨方法 超时了
     */
//    public static void moveZeroes(int[] nums) {
//        for (int i = 0; i < nums.length - 1; i++) {
//            if (nums[i] == 0) {
//                int currentNum = nums[i];
//                int nextNum = nums[i + 1];
//                if(nextNum == 0){
//                    extracted(nums, i + 1);
//                }
//                nums[i] = nums[i + 1];
//                nums[i + 1] = currentNum;
//            }
//        }
//        System.out.println(nums);
//    }
//
//    private static void extracted(int[] nums, int index) {
//        for (int j = index; j < nums.length - 1; j++) {
//            if(nums[j + 1] == 0){
//                extracted(nums, j + 1);
//            }
//            int forCurrentNum =  nums[j];
//            int forNext =  nums[j + 1];
//            nums[j] = forNext;
//            nums[j + 1] = forCurrentNum;
//        }
//    }
    public static void moveZeroes(int[] nums) {
        int n = nums.length, l = 0, r = 0;
        while (r < n) {
            if (nums[r] != 0) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                l++;
            }
            r++;
        }
    }


}
